#include <iostream>
#include <vector>
#include <random>

using namespace std;

// element type be any other type that could be compared using <, this PriorityQueue use int for demonstration only!

class PriorityQueue {
public:
    PriorityQueue() {}
    PriorityQueue(const vector<int>& data) {
        for (auto d:data) _q.push_back(d);
        for (int i = (data.size() >> 1); i >= 0; --i) {
            PercolateDown(i, _q[i], data.size());
        }
    }
    ~PriorityQueue() {
        _q.clear();
    }
    void push(int val) {
        _q.push_back(val);
        PercolateUp(_q.size() - 1, val);
    }
    int top() {
        return _q[0];
    }
    void pop() {
        _q[0] = _q.back();
        _q.pop_back();
        PercolateDown(0, _q[0], _q.size());
    }
    bool empty() {
        return _q.size() == 0;
    }
private:
    vector<int> _q;
    int LeftChild(int idx) {
        return (idx << 1) + 1;
    }
    int Parent(int idx) {
        return ((idx - 1) >> 1);
    }
    void PercolateDown(int idx, int val, int size) {
        int left_child = LeftChild(idx);
        while (left_child < size) {
            if ((left_child + 1) < size && _q[left_child] > _q[left_child + 1]) ++left_child;
            if (_q[left_child] < val) {
                _q[idx] = _q[left_child];
                idx = left_child;
            } else {
                break;
            }
            left_child = LeftChild(idx);
        }
        _q[idx] = val;
    }
    void PercolateUp(int idx, int val) {
        int parent = Parent(idx);
        while (parent > 0) {
            if (_q[parent] > val) {
                _q[idx] = _q[parent];
                idx = parent;
            } else break;
            idx = parent;
            parent = Parent(idx);
        }
        if (parent == 0 && idx != 0 && _q[parent] > val) {
            _q[idx] = _q[parent];
            idx = 0;
        }
        _q[idx] = val;
    }
};

int main()
{
    mt19937 rng;
    rng.seed(random_device()());
    uniform_int_distribution<mt19937::result_type> dist(10, 2000);
    vector<int> t;
    for (int i = 0; i < 1000; ++i) {
        t.push_back(dist(rng));
    }
    PriorityQueue pq(t);
    for (int i = 0; i < 1000; ++i) {
        pq.push(dist(rng));
    }
    int val;
    t.clear();
    while (!pq.empty()) {
        val = pq.top();
        t.push_back(val);
        pq.pop();
        //cout << val << " ";
    }
    //cout << endl;
    for (size_t i = 0; i < t.size(); ++i) {
        for (size_t j = i + 1; j < t.size(); ++j) {
            if (t[j] < t[i]) {
                cout << "PriorityQueue Fail!" << endl;
                return -1;
            }
        }
    }
    cout << "PriorityQueue Success" << endl;
    return 0;
}

